package com.li.algorithm.leetcode.hot100;


//class Position {
//    Integer row;
//    Integer col;
//    public Position(Integer row, Integer col) {
//        this.row = row;
//        this.col = col;
//    }
//}

public class Test18 {
    /**
     * 方法1：
     *   时间复杂度：O(m * n * (m + n))
     *   空间复杂度：O(m * n)
     */
//    public void setZeroes(int[][] matrix) {
//        //TODO:遍历所有位置，发现为零的，标记下来，再次遍历，行列赋零
//        ArrayList<Position> positions = new ArrayList<>();
//        for (int i = 0; i < matrix.length; i++) {
//            for (int j = 0; j < matrix[i].length; j++) {
//                if (matrix[i][j] == 0) {
//                    positions.add(new Position(i, j));
//                }
//            }
//        }
//        for (Position position : positions) {
//            for (int i = 0; i < matrix.length; i++) {
//                matrix[i][position.col] = 0;
//            }
//            Arrays.fill(matrix[position.row], 0);
//        }
//        for (int i = 0; i < matrix.length; i++) {
//            for (int j = 0; j < matrix[i].length; j++) {
//                System.out.print(matrix[i][j]);
//            }
//            System.out.println();
//        }
//    }

    /**
     * 方法2：原地算法
     *   用matrix第一行和第一列记录该行该列是否有0,作为标志位
     *   时间复杂度：O(m * n)
     *   空间复杂度：O(1)
     */
    public void setZeroes(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        boolean row0_flag = false;
        boolean col0_flag = false;
        //第一行是否含0
        for (int j = 0; j < col; j++) {
            if (matrix[0][j] == 0) {
                row0_flag = true;
                break;
            }
        }
        //第一列是否含0
        for (int i = 0; i < row; i++) {
            if (matrix[i][0] == 0) {
                col0_flag = true;
                break;
            }
        }
        // 把第一行第一列作为标志位
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        // 置0
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (row0_flag) {
            for (int j = 0; j < col; j++) {
                matrix[0][j] = 0;
            }
        }
        if (col0_flag) {
            for (int i = 0; i < row; i++) {
                matrix[i][0] = 0;
            }
        }
    }



    public static void main(String[] args) {
        new Test18().setZeroes(new int[][]{
                {0,1,2,0},
                {3,4,5,2},
                {1,3,1,5}
        });
    }
}
